package com.neusoft.ch4;

/*
 * 课堂笔记：
 *    1、冒泡排序算法
 *       算法思想：
 *          在一个无序的数组中，数组的元素从开始到最后，两两进行比较，根据比较规则交换位置，经过若干次（N-1）比较，
 *          最值会冒泡到数组的最后一个元素；
 *          经过若干轮（最多N轮）这样的处理，整个序列会变成一个有序序列。
 *       算法实现：
 *          双层循环嵌套进行实现。
 *          外层循环控制轮数；
 *          内存循环控制每一轮比较交换的次数；
 * 
 * 
 */

public class TestCh4 {

	public static void main(String[] args) {
		System.out.println("=============冒泡排序算法===============");
		sortBubble();
		System.out.println("=============冒泡排序算法：优化1===============");
		sortBubble2();
		System.out.println("=============冒泡排序算法：优化2===============");
		sortBubble3();
	}

	/**
	 * 冒泡排序算法:从小到大排序
	 * 优化外层比较轮数
	 */
	private static void sortBubble3() {
		// 定义要排序的数组
		//int[] arr0 = new int[] { 9, 5, 8, 4, 2, 0 };
		int[] arr0 = new int[] { 0, 2, 4, 5, 8, 9 };
		// 打印排序之后的数组内容
		System.out.println("排序之前：");
		// 打印数组
		for (int i : arr0) {
			System.out.print("  " + i);
		}
		// 换行
		System.out.println();
		
		// 统计比较的次数
		int count =0;
		
		// 临时变量
		int temp;
		// 冒泡排序算法
		// 外层for循环控制轮数（arr0.length轮）
		for (int i = 0; i < arr0.length; i++) {
			// 设置标志位：表示数列是否处于有序状态，默认有序
			boolean isSorted = true;
			
			// 内层for循环控制比较交换的次数：需要比较 arr0.length-1次
			for (int j = 0; j < arr0.length - 1 - i; j++) {
				// 两两比较，根据排序规则，交换位置
				// 排序规则：从小到大
				if (arr0[j] > arr0[j + 1]) {
					// 交换位置(异或位运算交换)
					temp = arr0[j];
					arr0[j] = arr0[j + 1];
					arr0[j + 1] = temp;
					
					// 发生了交换操作，说明当前数列还是无序状态，修改标志位的值
					isSorted = false;
				}
				
				// 比较次数计数器+1
				count++;
			}
			
			// 如果当前数列有序了，则终止外层for循环
			if(isSorted) {
				break;
			}
		}
		// 打印排序之后的数组内容
		System.out.println("排序之后：");
		// 打印数组
		for (int i : arr0) {
			System.out.print("  " + i);
		}
		// 换行
		System.out.println();
		// 打印本次排序比较的次数
		System.out.println("本次冒泡排序比较的次数："+count);
	}
	
	/**
	 * 冒泡排序算法:从小到大排序
	 * 优化内层比较次数
	 */
	private static void sortBubble2() {
		// 定义要排序的数组
		//int[] arr0 = new int[] { 9, 5, 8, 4, 2, 0 };
				int[] arr0 = new int[] { 0, 2, 4, 5, 8, 9 };
		// 打印排序之后的数组内容
		System.out.println("排序之前：");
		// 打印数组
		for (int i : arr0) {
			System.out.print("  " + i);
		}
		// 换行
		System.out.println();
		
		// 统计比较的次数
		int count =0;
		
		// 临时变量
		int temp;
		// 冒泡排序算法
		// 外层for循环控制轮数（arr0.length轮）
		for (int i = 0; i < arr0.length; i++) {
			// 内层for循环控制比较交换的次数：需要比较 arr0.length-1次
			for (int j = 0; j < arr0.length - 1 - i; j++) {
				// 两两比较，根据排序规则，交换位置
				// 排序规则：从小到大
				if (arr0[j] > arr0[j + 1]) {
					// 交换位置(异或位运算交换)
					temp = arr0[j];
					arr0[j] = arr0[j + 1];
					arr0[j + 1] = temp;
				}
				
				// 比较次数计数器+1
				count++;
			}
		}
		// 打印排序之后的数组内容
		System.out.println("排序之后：");
		// 打印数组
		for (int i : arr0) {
			System.out.print("  " + i);
		}
		// 换行
		System.out.println();
		// 打印本次排序比较的次数
		System.out.println("本次冒泡排序比较的次数："+count);
	}
	
	/**
	 * 冒泡排序算法:从小到大排序
	 */
	private static void sortBubble() {
		// 定义要排序的数组
		//int[] arr0 = new int[] { 9, 5, 8, 4, 2, 0 };
				int[] arr0 = new int[] { 0, 2, 4, 5, 8, 9 };
		// 打印排序之后的数组内容
		System.out.println("排序之前：");
		// 打印数组
		for (int i : arr0) {
			System.out.print("  " + i);
		}
		// 换行
		System.out.println();
		
		// 统计比较的次数
		int count = 0;
		// 临时变量
		int temp;
		// 冒泡排序算法
		// 外层for循环控制轮数（arr0.length轮）
		for (int i = 0; i < arr0.length; i++) {
			// 内层for循环控制比较交换的次数：需要比较 arr0.length-1次
			for (int j = 0; j < arr0.length - 1; j++) {
				// 两两比较，根据排序规则，交换位置
				// 排序规则：从小到大
				if (arr0[j] > arr0[j + 1]) {
					// 交换位置(异或位运算交换)
					temp = arr0[j];
					arr0[j] = arr0[j + 1];
					arr0[j + 1] = temp;
				}
				// 比较次数计数器+1
				count++;
			}
		}
		// 打印排序之后的数组内容
		System.out.println("排序之后：");
		// 打印数组
		for (int i : arr0) {
			System.out.print("  " + i);
		}
		// 换行
		System.out.println();
		// 打印本次排序比较的次数
				System.out.println("本次冒泡排序比较的次数："+count);
	}
	
	
}
